% AlgoDat ue5
% 21 May 2020

# Aufgabe 1

## (a)

The witness is bounded by the graph size and the verifier obviously correct. The complexity of the verifier is also bounded by the graph size, if a datastructure with efficient lookups for $v \in V$ is used. $\checkmark$

## (b)

Even though the witness is an empty string, it could be said the verifier uses the *witness* to verify whether the problem instance could be considered a "yes" instance. As learned throughout the course, Dijkstra's algorithm constructs the cheapest path in polynomial time, the result of which can then be utilized to verify for length *k*. $\checkmark$

## (c)

This is a classic optimality problem, as such, a single problem instance is not enough to answer for optimality. *X*

## (d)

It is not hard to see the correctness of the the certificate as well as certificate verification. The interesting part becomes the MST $T'$ as produced by Kruskal's or Prim's algorithm, which is not necessarily unique in the case of equally weighted edges within *G*. Because $T'$ is merely used to verify the weight of an MST, the verifier is also correct, because even for multiple valid MSTs, the weight has to be identical. The verifier is polynomially bounded. $\checkmark$

## (e)

Because it is asked whether *n* **is** a prime, the certificate represents a "no" instance. If it is a valid "no" instance, we can say for sure *n* is not prime, but the reverse is not necessarily true. *X*

# Aufgabe 2

$R_i$ ... respective reduction algorithm

$$ A \leq_P B, R_1 = O(n^3) $$

$$ B \leq_P C, R_2 = O(4^n) $$

$$ B \leq_P D, R_3 = O(n^2 \cdot log(n)) $$

## (a)

Given a problem instance $a \in A$, we can reduce the problem instance to one for problem *B* using algorithm $R_1$, the new problem instance *b* is then bounded by $b = O(n^3)$. We then choose reduction D over C because of the more favorable complexity of the reduction. As our problem instance is bounded by *b*, applying algorithm $R_3$ gives us a new problem instance bounded by $d = O((n^3)^2 \cdot log(n^3)) = O((n^3)^2 \cdot 3 log(n) = O((n^3)^2 \cdot log(n))$. *d* represents the tightest upper bound for a reduction to problem *D*.

## (b)

Given above reductions, we can conclude B to be *at least as hard*. Because Vertex Cover (VC) is known to be NP-complete, we can conclude *B* and analogously *D* to also be NP-complete. Whether *A* is in NP-complete cannot be certainly said, because *A* could potentially be in P, but we can conclude *A* to be at least in NP. As for *C*, because no known polynomial reduction exists, we cannot make any judgements about *C*.

## (c)

$$ C = O(n \cdot log_4(n)) $$

Our goal is to reduce *A* to whatever yields the tightest upper bound. We only know the time complexity of *C*, forcing us to choose *C*. Reducing $a \in A$ to $b = O(n^3)$ and then to $c = O(4^{(n^3)})$ gives us an upper boundary for a problem instance of *C*. Applying *C* therefore gives us a time complexity of $O(4^{(n^3)} \cdot log_4(4^{(n^3)})) = O(4^{(n^3)} \cdot n^3 \cdot log_4(4)) = O(4^{(n^3)} \cdot n^3)$.

# Aufgabe 3

To show NP-completess of 5-Color (5C), we need to prove two properties:

- 5C is in NP
- another NP-complete problem can be reduced to 5C

##### Certificate:

for graph $G = (V, E)$ exists a node coloring $N = (V, C)$, where $n \in N$ are tuples assigning a color $c \in C$ to node $v \in V$. *N* contains a coloring for every node, $\forall v \in V \exists c \in C : (v, c) \in N$

##### Verifier:

given a certificate of the specified kind, we check every two adjacent nodes for their color, a problem instance of 5C is valid if there are no two adjacent nodes of the same color, $\not\exists (v_1, v_2) \in E, (v_1, c_1) \in N, (v_2, c_2) \in N : c_1 = c_2$. The time complexity of such a verifier has to be polynomially bounded, because only *pairings* of nodes are compared.

We argue that 3-Color (3C), a known NP-complete problem, can be reduced to 5C using a simple trick:

- suppose 3C contains colors *A, B, C*
- take all nodes of color A and change half of them to a new color *D*, $D \not\in \{ A, B, C \}$
- take all nodes of color B and change half of them to a new color *E*, $D \not\in \{ A, B, C, D \}$

The new coloring contains at maximum all 5 colors. Assuming a problem instance of 3C is not correct, a reduced problem instance is also not going to be correct. Assuming a problem instance of 3C to be correct, it follows that no two nodes are colored with color *A* (analogous for *B*). Painting *all* of them with a new color would preserve this property. By painting only some, we introduce a new color without them neighbouring another.

The reduction is obviously possible in linear time and is correct.

We conclude that 5C must also be NP-complete.

# Aufgabe 4

Refer to scanned page at the end!

# Aufgabe 5

Refer to scanned page at the end!

# Aufgabe 6

To solve the problem, we first consider the individual trees with the roots $w_1, w_2, w_3, w_4$. For each of these trees, we find a maximal independent set, making use of *Independent-Set-In-A-Forest* as presented in our lectures. The question then becomes, which nodes of each independent set do we combine for a total maximal independent set? The only nodes we have to consider are the roots $w_1, w_2, w_3, w_4$, as all the children of one root node cannot be connected to any children of another root node. These roots are always arranged in a loop, offering us only two possibilities:

- take $w_1, w_3$
- take $w_2, w_4$

Whether a node $w_i, i \in [1, 4]$ is contained in their tree's respective independent set varies. As such, we verify for trees $T_1, T_3$ how many of the nodes $w_1, w_3$ are contained in their respective independent sets (analogously for $T_2, T_4$ and $w_2, w_4$). To maximize the amount of nodes we include, we check if *onethree* against *twofour*, where *onethree* represents how many of the nodes $w_1, w_3$ are in the independent sets of trees $T_1, T_3$ (analogously for *twofour*).

In a final step, if we choose *onethree* over *twofour*, we remove $w_2, w_4$ if they are contained. Likewise for *twofour*.

The algorithm, if implemented cleverly, is actually bounded by O(n). The reasoning is that each individual subtree takes linear time to find the maximal independent sets of, while the total graph consists of four such subtrees combined. The decision between the four root nodes is also linear in time, as such, the whole algorithm is bounded by O(n).

We also supply Pseudocode and an actual implementation in Python:

```
biggest_independent_set(T, w):
    independent_sets <- empty
    for T_i in T:
        independent_sets_i = independent-set-in-a-forest(T_i)

    onethree <- 0
    if independent_sets_0 contains w_0: onethree <- onethree + 1
    if independent_sets_2 contains w_2: onethree <- onethree + 1
    twofour <- 0
    if independent_sets_1 contains w_1: twofour <- twofour + 1
    if independent_sets_3 contains w_3: twofour <- twofour + 1

    if onethree >= twofour:
        remove w_1 from independent_sets_1
        remove w_3 from independent_sets_3
    else:
        remove w_0 from independent_sets_0
        remove w_2 from independent_sets_2

    return (independent_sets_1
        union independent_sets_2
        union independent_sets_3
        union independent_sets_4)
```

##### actual implementation

used to experimentally verify considerations:

```py
#!/usr/bin/env python3
import sys

# utility class
class Tree:
    def __init__(self, value):
        self.value = value
        self.children = list()

    # wrapper removing truth value from tuple
    def independent_set_in_tree(self):
        return self.independent_set()[1]

    # represents implementation of independent-set-in-a-forest
    # as presented in our lectures
    def independent_set(self):
        s = list()
        adjacent = False
        if self.children == list():
            s.append(self.value)
            return (False, s)
        for c in self.children:
            if c == None: continue
            cis = c.independent_set()
            if not cis[0]:
                adjacent = True
            [s.append(i) for i in cis[1]]
        if not adjacent:
            s.append(self.value)
        return (adjacent, s)

    def add(self, pair):
        if self.value == pair[0]:
            self.children.append(Tree(pair[1]))
            return
        [c.add(pair) for c in self.children]

    def __str__(self):
        return str(self.value) + ", (" + ", ".join(str(c) for c in self.children) + ")"

# wraps remove, as node is potentially not contained in list
def remove(nodes, node):
    try:
        nodes.remove(node)
    except ValueError:
        pass

# original algorithm!
def biggest_independent_sets(trees, w_i):
    # use independent-set-in-a-forest for all individual trees
    independent_sets = list()
    for tree in trees:
        independent_sets.append(tree.independent_set_in_tree())

    print("independent_sets:", independent_sets)

    onethree  = 1 if independent_sets[0][-1] == w_i[0] else 0
    onethree += 1 if independent_sets[2][-1] == w_i[2] else 0
    twofour   = 1 if independent_sets[1][-1] == w_i[1] else 0
    twofour  += 1 if independent_sets[3][-1] == w_i[3] else 0
    biggest_total_is = list()
    # decide between w_1, ..., w_4
    if onethree >= twofour:
        remove(independent_sets[1], w_i[1])
        remove(independent_sets[3], w_i[3])
    else:
        remove(independent_sets[0], w_i[0])
        remove(independent_sets[2], w_i[2])
    # append
    for independent_set in independent_sets:
        [biggest_total_is.append(s) for s in independent_set]

    return biggest_total_is

def main(lines):
    # parsing
    T = list()
    for line in lines.split("\n"):
        if line == "": continue
        E_i = list()
        V_i = list()
        for pair in line.split(" "):
            P = list(map(int, pair.split(",")))
            E_i.append((P[0], P[1]))
            V_i.append(P[0])
            V_i.append(P[1])
        T.append(E_i)
    print("graph:", T)

    # init
    trees = list()
    w_i = list()
    for subtree in T:
        root = subtree[0][0]
        tree = Tree(root)
        w_i.append(root)
        for pair in subtree:
            tree.add(pair)
        print("tree:", tree)
        trees.append(tree)

    print(biggest_independent_sets(trees, w_i))

if __name__ == '__main__':
    lines = sys.stdin.read()
    main(lines)
```

The graph was supplied as 4 independent trees, for which maximal independent sets are found using the algorithm *Independent-Set-In-A-Forest* presented in our lectures. The algorithm then takes their node count and maximizes them. The realization is that, only 2 of the nodes $w_1, w_2, w_3, w_4$ can be in an independent set, because they are *always* connected. The result is an independent set where either $w_1, w_3$ **or** $w_2, w_4$ are contained. Testing the above code yields the following result:

```sh
trlst@ayaya independent-set cat input | python3 is.py
graph: [[(1, 10), (10, 100), (10, 101)], [(2, 20), (20, 200)],
[(3, 30), (3, 31), (3, 32), (31, 310), (30, 300), (32, 320), (32, 321)],
[(4, 40), (4, 41), (41, 410)]]
tree: 1, (10, (100, (), 101, ()))
tree: 2, (20, (200, ()))
tree: 3, (30, (300, ()), 31, (310, ()), 32, (320, (), 321, ()))
tree: 4, (40, (), 41, (410, ()))
independent_sets: [[100, 101, 1], [200, 2], [300, 310, 320, 321, 3], [40, 410]]
[100, 101, 1, 200, 300, 310, 320, 321, 3, 40, 410]
```

The final line represents a list containing all the nodes that are in a maximal independent set. The graph is represented by its edges in the line beginning with `graph:`.
